package algorithm.array;

import util.GsonUtil;

import java.util.HashSet;
import java.util.Set;

/**
 * leetcode : https://leetcode.com/problems/set-matrix-zeroes/description/
 * 73. Set Matrix Zeroes
 * Difficulty : Medium
 *
 * 给一个方阵，遇到0的话，把横纵都置为0
 *
 * @Author Antony
 * @Since 2018/7/27 23:35
 */
public class SetMatrixZeros {

    public static void main(String[] args) {
        int[][] matrix = new int[5][];
        matrix[0] = new int[]{0,0,0,5};
        matrix[1] = new int[]{4,3,1,4};
        matrix[2] = new int[]{0,1,1,4};
        matrix[3] = new int[]{1,2,1,3};
        matrix[4] = new int[]{0,0,1,1};

        int[][] matrix_2 = new int[3][];
        matrix_2[0] = new int[]{1,2,5,5};
        matrix_2[1] = new int[]{4,0,0,4};
        matrix_2[2] = new int[]{4,1,1,4};

        setZeroes_oneSpace(matrix);
        System.out.println(GsonUtil.toJson(matrix));
    }

    /**
     * beats 100.0% - 1ms
     * 空间复杂度: O(1)
     * 把遇到0的横纵，存储在横纵的头部
     * 在第二遍遍历的时候，只遍历头部，，把该横纵都变为0即可
     *
     * 注意：
     * 横纵之中，要空出一个用于保存标记。
     * 否则如果matrix[0][0]=0的话，会把标记都清除为0，那么方阵所有元素就都为0了
     *
     * 在第二次设置0遍历时，需要从尾向头倒着遍历
     * 因为在第一次标记中有一列从0开始，如果这一列有0存在，那么也会标记全部清除为0
     *
     * 其实可以建议从1开始，加两个标记，横纵是否为0的标记。但是这样代码会多一些
     */
    public static void setZeroes_oneSpace(int[][] matrix) {
        int row = matrix.length;
        int col = matrix[0].length;
        boolean col0 = false;
        for(int i=0; i<row; i++){
            if(matrix[i][0]==0) col0 = true;
            for(int j=1; j<col; j++){
                if(matrix[i][j] == 0){
                    matrix[i][0] = matrix[0][j] = 0;
                }
            }
        }

        // 此处应该从尾向头倒着遍历，不然可能破坏头部的0标记位
        for(int i=row-1; i>=0; i--){
            for(int j=col-1; j>=1; j--){
                if(matrix[i][0]==0 || matrix[0][j]==0){
                    matrix[i][j]=0;
                }
            }
            if(col0) matrix[i][0] = 0;
        }

    }


    /**
     * beats 11.06 - 3ms
     * 空间复杂度: O(m+n)
     * 使用Set存储遇到0的横和纵列
     * 思路，遍历第一遍找到横纵有0的列
     * 然后再遍历将指定行列置为0
     */
    public static void setZeroes_space(int[][] matrix) {
        int height = matrix.length;
        int width = matrix[0].length;
        Set<Integer> heSet = new HashSet<>();
        Set<Integer> wdSet = new HashSet<>();
        for(int i=0; i<height; i++){
            for(int j=0; j<width; j++){
                if(matrix[i][j]==0){
                    heSet.add(i);
                    wdSet.add(j);
                }
            }
        }
        for(Integer hIdx : heSet){
            for(int i=0; i<width; i++){
                matrix[hIdx][i] = 0;
            }
        }
        for(Integer wIdx : wdSet){
            for(int j=0; j<height; j++){
                matrix[j][wIdx] = 0;
            }
        }
    }
}
